/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/5/24.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 6. Z 字形变换
 * 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
 *
 * 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
 *
 * L   C   I   R
 * E T O E S I I G
 * E   D   H   N
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
 *
 * 请你实现这个将字符串进行指定行数变换的函数：
 *
 * string convert(string s, int numRows);
 * 示例 1:
 *
 * 输入: s = "LEETCODEISHIRING", numRows = 3
 * 输出: "LCIRETOESIIGEDHN"
 * 示例 2:
 *
 * 输入: s = "LEETCODEISHIRING", numRows = 4
 * 输出: "LDREOEIIECIHNTSG"
 * 解释:
 *
 * L     D     R
 * E   O E   I I
 * E C   I H   N
 * T     S     G
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>

using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        int fetch_len = 0, ssize = s.size();
        int single_cols = numRows - 2;   /* 先得到单列 */
        int i = 0, j = 0;
        int row_tag = 0;
        string rows[numRows];
        while (fetch_len < ssize) {
            /* 首选正序输出 0~numRows 行 */
            row_tag = 0;
            for (i = numRows; i > 0 ; --i) {
                rows[row_tag] += s[fetch_len++];
                row_tag++;
                if(fetch_len >= ssize) goto END;
            }
            /* 接着反向输出 single_cols 行 */
            row_tag = numRows - 1;
            for (j = single_cols; j > 0; --j) {
                row_tag--;
                rows[row_tag] += s[fetch_len++];
                if(fetch_len >= ssize) goto END;
            }
        }
END:

        /* 拼接每一行，形成新的结果字符串 */
        string ans;
        for(string row : rows)
            ans.append(row);
        return ans;
    }
};

int main(void) {

    string str = "PAYPALISHIRING";
    Solution sol;
    string ans = sol.convert(str, 3);
    cout << "answer: " << ans << endl;
    return 0;
}

